{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。\n",
    "\n",
    "注意：答案中不可以包含重复的三元组。\n",
    "\n",
    " \n",
    "\n",
    "示例：\n",
    "\n",
    "给定数组 nums = [-1, 0, 1, 2, -1, -4]，\n",
    "\n",
    "满足要求的三元组集合为：\n",
    "[\n",
    "  [-1, 0, 1],\n",
    "  [-1, -1, 2]\n",
    "]\n",
    "\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/3sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-1, -1, 2], [-1, 0, 1]]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def threeSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        rnums=[]              # 创建一个要返回的新列表\n",
    "        nums.sort()       #　排序\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if i > 0 and nums[i] == nums[i-1]: # 避免重复项\n",
    "                  continue\n",
    "            if nums[i] > 0:# 减少无关计算，定值大于 0 后，后面的都大于 0，没必要进行计算了\n",
    "                break\n",
    "            left = i + 1\n",
    "            right = n -1\n",
    "            while left < right:    \n",
    "                cur_num = nums[i] + nums[left] + nums[right]\n",
    "                if cur_num == 0:\n",
    "                    tmp = [nums[i], nums[left], nums[right]]\n",
    "                    rnums.append(tmp)\n",
    "                    while left < right and nums[left]==nums[left+1]: # 去重\n",
    "                        left += 1\n",
    "                    while left < right  and nums[right]==nums[right-1]: # 去重\n",
    "                        right -= 1\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                elif cur_num > 0:\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "        return rnums\n",
    "                \n",
    "        \n",
    "if __name__ == \"__main__\":\n",
    "    nums = [-1, 0, 1, 2, -1, -4]\n",
    "    Sol = Solution()\n",
    "    end = Sol.threeSum(nums)\n",
    "    print(end)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 原理\n",
    "## 先将数组进行排序\n",
    "## 从左侧开始逐渐选取一个值为定值\n",
    "##    从右侧剩余的值中获取的与前面定值相加为 0 的两个值\n",
    "##         首尾与定值相加\n",
    "##             等于 0，记录这三个值\n",
    "##             小于 0，首部右移\n",
    "##             大于 0，尾部左移\n",
    "## 定值右移，重复该步骤"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
